package com.beautiful.xin.sort;

import com.google.common.collect.Lists;

import javax.swing.*;
import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xuqingxin 2021/8/9 11:18 上午
 */
public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = {10, 20, 20, 30, 40, 50, 60, 60};
        int target = 90;

        List<List<Integer>> threesum = threesum(nums, target);
        System.out.println(threesum);

        List<List<Integer>> three = three(nums, target);
        System.out.println(three);

    }

    public static List<List<Integer>> threesum(int[] nums, int target) {
        List<List<Integer>> result = Lists.newArrayList();
        if (nums == null || nums.length < 3) return result;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > target) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    result.add(Lists.newArrayList(nums[i], nums[j], nums[k]));
                    while (j < k && nums[j] == nums[j + 1]) j++;
                    while (j < k && nums[k] == nums[k - 1]) k--;
                    j++;
                    k--;
                } else if (sum > target) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return result;
    }

    public static List<List<Integer>> three(int[] a, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(a);
        for (int i = 0; i < a.length; i++) {
            if (a[i] > target) break;
            if (i > 0 && a[i] == a[i - 1]) continue;
            int j = i + 1;
            int k = a.length - 1;
            while (j < k) {
                int sum = a[i] + a[j] + a[k];
                if (sum == target) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(a[i]);
                    temp.add(a[j]);
                    temp.add(a[k]);
                    result.add(temp);
                    while (j < k && a[j] == a[j + 1]) j++;
                    while (j < k && a[k] == a[k - 1]) k--;
                    j++;
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return result;
    }
}
